package Hot_100;

import org.junit.Test;

/**
 * @Description
 * @Author Firenut
 * @Date 2023-07-10 22:08
 */
public class T33_search1 {
    @Test
    public void test() {
        System.out.println(search(new int[]{3, 1}, 1));
    }

    // 旋转后的数组,总有一边是有序的
    // 如果nums[left]<nums[mid],说明左半区是有序,否则右半区是有序的
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            // 下面应该是 <=,如果出现 nums[left] == nums[mid],说明 left == mid
            // 因为题目说了数组是升序的;如果写成 <,那么会丢弃掉左半区，直接去判断右半区，显然是不对的
            // case : {3, 1}, 1
            if (nums[left] <= nums[mid]) {
                // 左边有序
                if (nums[left] <= target && target <= nums[mid]) {
                    // 二分查找
                    return binarySearch(nums, left, mid, target);
                }
                // 到右边查找
                left = mid + 1;
            } else {
                // 右边有序
                // 如果target在右半区
                if (nums[mid] <= target && target <= nums[right]) {
                    // 二分查找
                    return binarySearch(nums, mid, right, target);
                }
                // 到左边查找
                right = mid - 1;
            }
        }
        return -1;
    }

    int binarySearch(int[] nums, int left, int right, int target) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] == target) {
                return mid;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}
